package com.leetcode.easy;

import com.leetcode.entity.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author zfl
 * @Classname SolutionIsSameTree
 * @Description 判断两个树是否是相同的树
 * @Date 2020/9/2 15:12
 * @Created by zfl
 */
public class SolutionIsSameTree {

    /**
     * @param p
     * @param q
     * @return
     * 深度优先搜索 + 递归
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：37.3 MB, 在所有 Java 提交中击败了33.54%的用户
     */
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null) {
            return true;
        }else if(p == null || q == null) {
            return false;
        }else if(p.val != q.val) {
            return false;
        }else {
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        }
    }

    public boolean isSameTree2(TreeNode p, TreeNode q) {
        if(p == null && q == null) {
            return true;
        }else if(p == null || q == null) {
            return false;
        }
        Queue<TreeNode> queue1 = new LinkedList<>();
        Queue<TreeNode> queue2 = new LinkedList<>();
        queue1.offer(p);
        queue2.offer(q);
        while(!queue1.isEmpty() && !queue2.isEmpty()) {
            TreeNode node1 = queue1.poll();
            TreeNode node2 = queue2.poll();
            if(node1.val != node2.val) {return false;}
            TreeNode left1 = node1.left, right1 = node1.right, left2 = node2.left, right2 = node2.right;
            if(left1 == null ^ left2 == null) {return false;}
            if(right1 == null ^ right2 == null) {return false;}
            if(left1 != null) {
                queue1.offer(left1);
            }
            if(right1 != null) {
                queue1.offer(right1);
            }
            if(left2 != null) {
                queue2.offer(left2);
            }
            if(right2 != null) {
                queue2.offer(right2);
            }
        }
        return queue1.isEmpty() && queue2.isEmpty();
    }
}
